package review;

import ListNode.ListNode;

import java.util.HashSet;
import java.util.Set;

public class TestYesterday {
    //最短路径
    public int getMinPath(int[][] a){
        if(a.length==0||a[0].length==0||a==null){
            return 0;
        }
        int row=a.length;
        int cols=a[0].length;
        int[][] db=new int[row][cols];
        db[0][0]=a[0][0];
        for(int i=1;i<row;i++){
            db[i][0]=db[i-1][0]+a[i][0];
        }
        for(int j=1;j<cols;j++){
            db[0][j]=db[0][j-1]+a[0][j];
        }
        for(int i=1;i<row;i++){
            for(int j=1;j<cols;j++){
                db[i][j]=Math.min(db[i-1][j],db[i][j-1])+a[i][j];
            }
        }
        return db[row-1][cols-1];
    }

    //找环
    /*public ListNode  getH(ListNode head){
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                    ListNode slow2=head;
                    while(slow2!=slow){
                        slow=slow.next;
                        slow2=slow2.next;
                    }
                    return slow;
            }
        }
        return null;
    }*/
    //利用集合找环
   /* public ListNode getH2(ListNode head){
        ListNode node=head;
        Set<ListNode> set=new HashSet<>();
        while(node!=null){
            if(!set.add(node)){
                return node;
            }
            node=node.next;
        }
        return null;
    }*/
    public static void main(String[] args){
        int[][] a={{1,3,5,9},{8,1,3,4},{5,0,6,1},{8,8,4,0}};
        System.out.print(new TestYesterday().getMinPath(a));
    }
}
